package de.tum.wi.som;

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

import umontreal.iro.lecuyer.stat.Tally;

//http://www.iro.umontreal.ca/~simardr/ssj/indexe.html

public class Project {
	private Node source; // dummy source node

	private Node[] nodes; // non-dummy nodes

	private Node sink; // dummy sink node

	int[] R; // resource availability

	private double anchor;

	private String name;

	// whether the project graph including earliest start etc. is calculated
	// already
	private boolean isCalculated;

	public Project(String name, Node source, Node[] nodes, Node sink, int[] R) {
		this.name = name;
		this.source = source;
		this.nodes = nodes;
		this.sink = sink;
		this.R = R;
		this.isCalculated = false;
	}

	public double[][] calcLongestPath() {
		// calculate forward schedule with Triple algorithm
		ArrayList<Node> network = new ArrayList<Node>();
		network.add(source);
		network.addAll(Arrays.asList(nodes));
		network.add(sink);
		double[][] ret = new double[network.size()][network.size()];

		// init adjacency matrix
		for (int i = 0; i < network.size(); i++) {
			ret[i][i] = 0;
			for (int j = 0; j < network.size(); j++)
				ret[i][j] = Integer.MIN_VALUE;
		}
		for (Node i : network)
			for (Node j : i.successors)
				ret[network.indexOf(i)][network.indexOf(j)] = i.d;
		for (int j = 0; j < network.size(); j++) {
			ret[0][j] = 0;
		}

		// run iterations of Warshall's algorithm
		for (int k = 0; k < network.size(); k++) {
			for (int i = 0; i < network.size(); i++) {
				if (i == k || ret[i][k] == Integer.MIN_VALUE)
					continue;
				for (int j = 0; j < network.size(); j++) {
					if (j == k || j == i || ret[k][j] == Integer.MIN_VALUE)
						continue;
					if (ret[i][j] < ret[i][k] + ret[k][j])
						ret[i][j] = ret[i][k] + ret[k][j];
				}
			}
		}
		return ret;
	}

	public boolean[][] calcTransitiveReduction() {
		// calculate transitive reduction with Warshall's algorithm
		ArrayList<Node> network = new ArrayList<Node>();
		network.add(source);
		network.addAll(Arrays.asList(nodes));
		network.add(sink);
		boolean[][] ret = new boolean[network.size()][network.size()];

		// init adjacency matrix
		for (Node i : network)
			for (Node j : i.successors)
				ret[network.indexOf(i)][network.indexOf(j)] = true;

		// run iterations of Warshall's algorithm
		for (int k = 0; k < network.size(); k++)
			for (int i = 0; i < network.size(); i++)
				for (int j = 0; j < network.size(); j++)
					ret[i][j] = ret[i][j] && !(ret[i][k] && ret[k][j]);
		return ret;
	}

	public boolean[][] calcTransitiveClosure() {
		// calculate reachability matrix with Warshall's algorithm
		ArrayList<Node> network = new ArrayList<Node>();
		network.add(source);
		network.addAll(Arrays.asList(nodes));
		network.add(sink);
		boolean[][] ret = new boolean[network.size()][network.size()];

		// init adjacency matrix
		for (Node i : network)
			for (Node j : i.successors)
				ret[network.indexOf(i)][network.indexOf(j)] = true;

		// run iterations of Warshall's algorithm
		for (int k = 0; k < ret.length; k++)
			for (int i = 0; i < ret.length; i++)
				for (int j = 0; j < ret.length; j++)
					ret[i][j] = ret[i][j] || (ret[i][k] && ret[k][j]);
		return ret;
	}

	public double calcC() {
		// Calculation of Network Complexity metric for project
		boolean[][] red = calcTransitiveReduction();
		int count = 0;
		for (boolean[] a : red)
			for (boolean b : a)
				if (b)
					count++;

		return (double) count / (nodes.length + 2);
	}

	public double calcRS() {
		// Calculation of Resource Strength metric for project
		double[] distance = calcLongestPath()[0];
		int kmin = 0, kmax = 0, kcur = 0;
		Tally tally = new Tally();
		Double temp = new Double(0);

		Node[] network = new Node[nodes.length + 2];
		network[0] = source;
		for (int i = 1; i < network.length - 1; i++)
			network[i] = nodes[i - 1];
		network[network.length - 1] = sink;
		// calculate kmin/max for all resources
		for (int r = 0; r < R.length; r++) {
			kmin = 0;
			kmax = 0;
			for (int i = 0; i < network.length; i++) {
				kcur = 0;
				for (int j = 1; j < network.length - 1; j++)
					if (distance[j] <= distance[i]
							&& distance[i] < distance[j] + network[j].d)
						kcur += (network[j].r)[r];
				if (kmax < kcur)
					kmax = kcur;
			}
			for (Node n : nodes)
				if ((n.r)[r] > kmin)
					kmin = (n.r)[r];
			temp = new Double((double) (R[r] - kmin) / (kmax - kmin));
			if (!temp.isNaN())
				tally.add(temp);
		}
		return tally.average();
	}

	public double calcRF() {
		// Calculation of Resource Factor metric for project
		int res_count = R.length, node_count = nodes.length + 2, count = 0;
		for (Node n : nodes)
			for (int k : n.r)
				if (k > 0)
					count++;
		return (double) 1 / (node_count - 2) * 1 / res_count * count;
	}

	public void resetStart() {
		source.start = Double.POSITIVE_INFINITY;
		for (Node n : nodes)
			n.start = Double.POSITIVE_INFINITY;
		sink.start = Double.POSITIVE_INFINITY;
	}

	public void parallelSGS(Node[] prioList) {
		ArrayList<Node> list = new ArrayList<Node>(); // Prevent overwriting
														// original priority
														// list
		list.addAll(Arrays.asList(prioList));
		ArrayList<Node> A = new ArrayList<Node>(); // list of active activities
		int[] R = this.R.clone(); // Prevent overwriting original maximal
									// resource availability
		double t = 0;
		source.start = t;
		A.add(source);

		while (list.size() > 0) {
			// Advance t to next activity finish time and update resources
			t = Double.POSITIVE_INFINITY;
			for (Node n : A)
				t = t > (n.start + n.d) ? n.start + n.d : t;
			for (int j = 0; j < A.size(); j++)
				if (A.get(j).start + A.get(j).d <= t) {
					for (int k = 0; k < R.length; k++)
						R[k] += A.get(j).r[k];
					A.remove(j);
					j--;
				}

			taskCheck: for (int i = 0; i < list.size(); i++) {
				// if activity i is precedence feasible...
				for (Node pred : list.get(i).predecessors)
					if (pred.start + pred.d > t)
						continue taskCheck;
				// and resource feasible...
				for (int k = 0; k < R.length; k++)
					if (R[k] < list.get(i).r[k]) {
						continue taskCheck;
					}
				// start activity
				list.get(i).start = t;
				for (int k = 0; k < R.length; k++)
					R[k] -= list.get(i).r[k];
				A.add(list.remove(i));
				i--;
			}
		}
		for (Node n : sink.predecessors)
			sink.start = sink.start < (n.start + n.d) ? n.start + n.d
					: sink.start;
	}

	public void stochasticSerialSGS(Node[] prioList) {
		ArrayList<Node> A = new ArrayList<Node>(); // list of active activities
		int[] R = this.R.clone(); // Prevent overwriting original maximal
									// resource availability
		double t = 0;
		source.start = t;
		A.add(source);

		for (Node i : prioList) {
			timeCheck: while (i.start == Double.POSITIVE_INFINITY) {
				// Advance t to next activity finish time and update resources
				t = Double.POSITIVE_INFINITY;
				for (Node n : A)
					t = t > (n.start + n.d) ? n.start + n.d : t;
				for (int j = 0; j < A.size(); j++)
					if (A.get(j).start + A.get(j).d <= t) {
						for (int k = 0; k < R.length; k++)
							R[k] += A.get(j).r[k];
						A.remove(j);
						j--;
					}
				// if activity i is precedence feasible...
				for (Node pred : i.predecessors)
					if (pred.start + pred.d > t)
						continue timeCheck;
				// and resource feasible...
				for (int k = 0; k < R.length; k++)
					if (R[k] < i.r[k]) {
						continue timeCheck;
					}
				// start activity
				i.start = t;
				for (int k = 0; k < R.length; k++)
					R[k] -= i.r[k];
				A.add(i);
			}
		}
		for (Node n : sink.predecessors)
			sink.start = sink.start < (n.start + n.d) ? n.start + n.d
					: sink.start;
	}

	public static Project readProject(InputStream in, String name)
			throws IOException {
		// Generation of Project Object from .RCP file
		Node source;
		Node[] nodes;
		Node sink;
		int nr_nodes;
		int nr_res;
		int[] res;
		int[][] succ;
		int d;
		int[] k;
		Scanner sc = new Scanner(in);
		sc.useDelimiter(System.getProperty("line.separator"));
		Scanner line_sc;

		// read # of nodes and # of resources
		line_sc = new Scanner(sc.next());
		nr_nodes = line_sc.nextInt();
		nodes = new Node[nr_nodes - 2];
		nr_res = line_sc.nextInt();
		succ = new int[nr_nodes - 1][];

		// read resource availability
		res = new int[nr_res];
		line_sc = new Scanner(sc.next());
		for (int i = 0; i < res.length; i++)
			res[i] = line_sc.nextInt();

		// dummy source
		line_sc = new Scanner(sc.next());
		d = Integer.parseInt(line_sc.next());
		k = new int[nr_res];
		for (int i = 0; i < k.length; i++)
			k[i] = line_sc.nextInt();
		succ[0] = new int[line_sc.nextInt()];
		for (int i = 0; i < succ[0].length; i++)
			succ[0][i] = line_sc.nextInt();
		source = new Node(d, k);

		// create nodes and record precedences
		for (int j = 1; j < nr_nodes - 1; j++) {
			line_sc = new Scanner(sc.next());
			d = Integer.parseInt(line_sc.next());
			k = new int[nr_res];
			for (int i = 0; i < k.length; i++)
				k[i] = line_sc.nextInt();
			succ[j] = new int[line_sc.nextInt()];
			for (int i = 0; i < succ[j].length; i++)
				succ[j][i] = line_sc.nextInt();
			nodes[j - 1] = new Node(d, k);
		}

		// dummy sink
		line_sc = new Scanner(sc.next());
		d = Integer.parseInt(line_sc.next());
		k = new int[nr_res];
		for (int i = 0; i < k.length; i++)
			k[i] = line_sc.nextInt();
		sink = new Node(d, k);

		// add precedence relations to network
		for (int i : succ[0]) {
			if (i == nr_nodes)
				Node.addArc(source, sink);
			else
				Node.addArc(source, nodes[i - 2]);
		}
		for (int i = 1; i < succ.length; i++) {
			for (int j : succ[i]) {
				if (j == nr_nodes)
					Node.addArc(nodes[i - 1], sink);
				else
					Node.addArc(nodes[i - 1], nodes[j - 2]);
			}
		}
		return new Project(name, source, nodes, sink, res);
	}

	/**
	 * Calculates earliest start, finish and latest start, finish for all nodes
	 * in the project.
	 * 
	 */
	public void calcProjectGraph() {
		if (isCalulated())
			return;
		Node[] nodes = getNodes();
		double[][] adjMatrix = calcLongestPath();
		for (int i = 1; i < adjMatrix.length - 1; i++) {
			nodes[i - 1].setEarliestStart(adjMatrix[0][i]);
			nodes[i - 1].setEarliestFinish(adjMatrix[0][i]
					+ nodes[i - 1].getD());
		}
		Node[] nodeCopy = Arrays.copyOf(nodes, nodes.length);
		
		double tMax = 0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].getEarliestStart() + nodes[i].getD() > tMax) {
				tMax = nodes[i].getEarliestStart() + nodes[i].getD();
			}
		}
		getSink().setLatestStart(tMax);
		getSink().setEarliestStart(tMax);
		getSink().setLatestFinish(tMax);
		getSink().setEarliestFinish(tMax);
		// compute latest start and finish
		Set<Node> completedNodes = new HashSet<Node>();
		completedNodes.add(getSink());
		Set<Node> remainingNodes = new HashSet<Node>();
		remainingNodes.addAll(Arrays.asList(nodes));
		Set<Node> nodesToAdd;

		// iterate backwards over graph. latest start of a node is the latest
		// start of the predecessor minus the node's
		// duration
		while (!remainingNodes.isEmpty()) {
			nodesToAdd = new HashSet<Node>();
			for (Node completedNode : completedNodes) {
				for (Node pred : completedNode.getPredecessors()) {
					// if node has not been treated yet, update ls and lf and
					// add it to the completed nodes and remove
					// it from the remaining ones
					if (pred.getLatestStart() == 0) {
						pred.setLatestStart(completedNode.getLatestStart()
								- pred.getD());
						pred.setLatestFinish(completedNode.getLatestStart());
						nodesToAdd.add(pred);
						remainingNodes.remove(pred);
					} else {
						// if node has been treated already check whether an
						// update is necessary, no need to add it to
						// the completed nodes, it's already there
						if (pred.getLatestStart() > completedNode
								.getLatestStart() - pred.getD()) {
							pred.setLatestStart(completedNode.getLatestStart()
									- pred.getD());
							pred.setLatestFinish(completedNode.getLatestStart());
						}
					}
				}
			}
			// add all newly finished nodes to the completedNodes
			completedNodes.addAll(nodesToAdd);
		}
		setCalculated(true);
	}

	private void setCalculated(boolean b) {
		isCalculated = true;

	}

	private boolean isCalulated() {
		return isCalculated;
	}

	@Deprecated
	/**
	 * Depreceated: Use PrioUtil.determineAccessibleNodes instead within algorithm
	 * to make sure constraints are taken into account correctly.
	 *
	 * Takes a prioritized array of nodes and sorts them according to
	 * constraints, i.e. for a node to be at a position in the node array, all
	 * it's predecessors are already at a previous position in the node array.
	 * The newly sorted array is then set as the node array for the project.
	 *
	 * @param nodes prioritized array of nodes
	 */
	public void sortNodesConsideringConstraints(Node[] nodes) {
		ArrayList<Node> nodeList = new ArrayList<Node>();
		nodeList.addAll(Arrays.asList(nodes));
		this.sortNodesConsideringConstraints(nodeList);
	}

	@Deprecated
	/**
	 * Depreceated: Use PrioUtil.determineAccessibleNodes instead within algorithm
	 * to make sure constraints are taken into account correctly.
	 *
	 * Takes a prioritized list of nodes and sorts them according to constraints, i.e. for a node to be at a position in
	 * the node array, all it's predecessors are already at a previous position in the node array. The newly sorted
	 * array is then set as the node array for the project.
	 *
	 * @param nodes
	 *            prioritized list of nodes
	 */
	public void sortNodesConsideringConstraints(List<Node> nodes) {
		List<Node> scheduledActivities = new ArrayList<Node>();
		scheduledActivities.add(this.getSource());
		while (!nodes.isEmpty()) {
			Iterator<Node> nodeIterator = nodes.iterator();
			predCheck: while (nodeIterator.hasNext()) {
				Node n = nodeIterator.next();
				for (Node predecessor : n.getPredecessors()) {
					if (!scheduledActivities.contains(predecessor))
						continue predCheck;
				}
				nodeIterator.remove();
				scheduledActivities.add(n);
			}
		}
		scheduledActivities.remove(this.getSource());

		this.setNodes(scheduledActivities.toArray(new Node[scheduledActivities
				.size()]));
	}

	public List<Node> getCriticalPath() {
		calcProjectGraph();
		List<Node> criticalPath = new ArrayList<Node>();
		for (Node n : nodes) {
			if (n.getSlack() == 0)
				criticalPath.add(n);
		}
		return criticalPath;
	}

	/**
	 * Copies a whole project including all node attributes, anchor predecessor
	 * and successor relationships.
	 * 
	 * @return Copy of the project including all node attributes, anchor,
	 *         predecessor and successor relationships.
	 */
	public Project getCopyOfProject() {
		Map<Node, Node> oldNewNodeRelation = new HashMap<Node, Node>();
		Node[] newNodes = new Node[nodes.length];
		for (int i = 0; i < nodes.length; i++) {
			newNodes[i] = nodes[i].getCopyOf();
			oldNewNodeRelation.put(nodes[i], newNodes[i]);
		}

		// add source and sink
		Node newSource = source.getCopyOf();
		oldNewNodeRelation.put(source, newSource);
		Node newSink = sink.getCopyOf();
		oldNewNodeRelation.put(sink, newSink);

		for (int i = 0; i < nodes.length; i++) {
			Node oldNode = nodes[i];
			Node newNode = oldNewNodeRelation.get(oldNode);

			// add predecessors
			List<Node> newPredecessors = new ArrayList<Node>();
			for (Node predecessor : oldNode.getPredecessors()) {
				newPredecessors.add(oldNewNodeRelation.get(predecessor));
			}
			newNode.setPredecessors(newPredecessors);

			// add successors
			List<Node> newSuccessors = new ArrayList<Node>();
			for (Node successor : oldNode.getSuccessors()) {
				newSuccessors.add(oldNewNodeRelation.get(successor));
			}
			newNode.setSuccessors(newSuccessors);

		}

		// add source
		List<Node> newSourceSuccessors = new ArrayList<Node>();
		for (Node successor : source.getSuccessors()) {
			newSourceSuccessors.add(oldNewNodeRelation.get(successor));
		}
		newSource.setSuccessors(newSourceSuccessors);
		newSource.setPredecessors(new ArrayList<Node>());

		// add sink
		List<Node> newSinkPredecessors = new ArrayList<Node>();
		for (Node predecessor : sink.getPredecessors()) {
			newSinkPredecessors.add(oldNewNodeRelation.get(predecessor));
		}
		newSink.setPredecessors(newSinkPredecessors);
		newSink.setSuccessors(new ArrayList<Node>());

		Project projectCopy = new Project(name, newSource, newNodes, newSink,
				Arrays.copyOf(R, R.length));

		projectCopy.setAnchor(getAnchor());
		projectCopy.setCalculated(isCalulated());

		return projectCopy;
	}

	public Node getSource() {
		return source;
	}

	public void setSource(Node source) {
		this.source = source;
	}

	public Node[] getNodes() {
		return nodes;
	}

	public void setNodes(Node[] nodes) {
		this.nodes = nodes;
	}

	public Node getSink() {
		return sink;
	}

	public void setSink(Node sink) {
		this.sink = sink;
	}

	public int[] getR() {
		return R;
	}

	public void setR(int[] r) {
		R = r;
	}

	public void calculateAnchor() {
		// anchor = duration of nodes in critical path
		List<Node> criticalPath = getCriticalPath();
		double anchor = 0;
		for (Node n : criticalPath) {
			anchor += n.getD();
		}
		this.anchor = anchor;

	}

	public double getAnchor() {
		return anchor;
	}

	public void setAnchor(double anchor) {
		this.anchor = anchor;
	}

	public double getMakespan() {
		double makespan = 0;
		for (Node n : nodes) {
			if (n.getStart() + n.getD() > makespan)
				makespan = n.getStart() + n.getD();
		}
		return makespan;
	}

	public String getName() {
		return name;
	}

}
